Inégalité de Hoeffding

En théorie des probabilités, l’inégalité de Hoeffding est une inégalité de concentration concernant les sommes de variables aléatoires indépendantes et bornées. Elle tire son nom du mathématicien et statisticien finlandais Wassily Hoeffding. Il existe une version plus générale de cette inégalité, concernant une somme d'accroissements de martingales, accroissements là encore bornés : cette version plus générale est parfois connue sous le nom d'inégalité d'Azuma-Hoeffding.

Énoncé

Inégalité de Hoeffding — Soit une suite $\ (X_{k})_{1\leq k\leq n}\$ de variables aléatoires réelles indépendantes vérifiant, pour deux suites $\ (a_{k})_{1\leq k\leq n},\$ $\ (b_{k})_{1\leq k\leq n}\$ de nombres réels tels que $\ a_{k}<b_{k},\$

$\forall k,\qquad \mathbb {P} (a_{k}\leq X_{k}\leq b_{k})=1.$

On pose

$S_{n}=X_{1}+X_{2}+\dots +X_{n}.$

Alors, pour tout $\ t>0,\$

${\begin{array}{rl}\mathbb {P} \left(S_{n}-\mathbb {E} [S_{n}]\geq t\right)&\leq \exp \left(-{\frac {2\,t^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right),\\\mathbb {P} \left(S_{n}-\mathbb {E} [S_{n}]\leq -t\right)&\leq \exp \left(-{\frac {2\,t^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right),\\\mathbb {P} \left(\left|S_{n}-\mathbb {E} [S_{n}]\right|\geq t\right)&\leq 2\exp \left(-{\frac {2\,t^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right).\end{array}}$

Bornes pour la dispersion de la loi binomiale de paramètres n et p=0,5, obtenues respectivement à l'aide de l'inégalité de Bienaymé-Tchebychev et à l'aide de l'inégalité de Hoeffding.

Cas de la loi binomiale

Dans cette section, nous allons comparer l'inégalité de Hoeffding et l'inégalité de Bienaymé-Tchebychev dans le cas de la loi binomiale. Supposons que pour tout k entre 1 et n, on ait

$\mathbb {P} (X_{k}=1)=1-\mathbb {P} (X_{k}=0)=p.$

Alors $\ S_{n}\$représente le nombre de piles obtenus à un jeu de pile ou face avec n lancers et où p est la probabilité d'avoir pile sur un lancer. $\ S_{n}\$ suit la loi binomiale de paramètres n et p. Nous avons les inégalités suivantes, pour tout $x>0$ :

• L'inégalité de Bienaymé-Tchebychev donne : $\mathbb {P} \left(\left|S_{n}-\mathbb {E} [S_{n}]\right|\geq x{\sqrt {n}}\right)\leq {\frac {p(1-p)}{x^{2}}},$
• L'inégalité de Hoeffding donne $\mathbb {P} \left(\left|S_{n}-\mathbb {E} [S_{n}]\right|\geq x{\sqrt {n}}\right)\leq 2\exp \left(-2\,x^{2}\right)$.

On voit que dans ce cas (et c'est assez représentatif de la situation générale^{[réf. nécessaire]}) l'inégalité de Hoeffding est beaucoup plus précise pour $\ x\$ suffisamment grand.

Démonstration

Inégalité préliminaire

La démonstration fait usage de la proposition suivante :

Proposition —  Soit $\ Y\$ une variable aléatoire réelle bornée et centrée (vérifiant $\ \mathbb {E} [Y]=0\$). Soit $\ c,\,d\$ deux nombres réels tels que $\ c<d\$ et tels que $\ \mathbb {P} (c\leq Y\leq d)=1.\$ Alors, pour tout réel $\ s>0,\$

$\mathbb {E} \left[e^{sY}\right]\leq \exp \left(s^{2}(d-c)^{2}/8\right).$

D'abord, on peut supposer c < 0 et d > 0. En effet, si $c\geq 0$, alors Y est une variable aléatoire presque-sûrement positive d'espérance nulle, donc Y=0 presque-sûrement et la proposition est évidente ; le raisonnement est analogue pour $d\leq 0.$ Par convexité de la fonction $\ x\mapsto e^{sx},\$ on a, pour $\ c\leq Y(\omega )\leq d,\$

$e^{sY(\omega )}\leq {\frac {d-Y(\omega )}{d-c}}\ e^{sc}\ +\ {\frac {Y(\omega )-c}{d-c}}\ e^{sd}.$

En passant à l'espérance, puisque $\ \mathbb {P} (c\leq Y\leq d)=1,\$ on en déduit que

$\mathbb {E} [e^{sY}]\leq f(s)={\frac {d}{d-c}}\ e^{sc}\ +\ {\frac {-c}{d-c}}\ e^{sd}.$

On pose

${\begin{array}{rl}(d-c)s&=u\\\ln(f(s))&=\psi (u),\\{\frac {-c}{d-c}}&=p,\quad 1-p={\frac {d}{d-c}}.\end{array}}$

Puisque c < 0 et d > 0, on a bien $p\in [0,1]$ d'où la pertinence de la notation. Il suit que

$\psi (u)\,=\,-pu+\ln \left(1-p+pe^{u}\right).$

On remarque alors que $\ \psi (0)=\psi ^{\prime }(0)=0.\$ De plus

$\psi ^{\prime \prime }(u)={\frac {\left(1-p\right)pe^{u}}{\left(1-p+pe^{u}\right)^{2}}}={\frac {\alpha \beta }{(\alpha +\beta )^{2}}}\leq {\frac {1}{4}}.$

Alors, en vertu de la formule de Taylor-Lagrange à l'ordre 1,

$\psi (u)=\psi (0)+\psi ^{\prime }(0)u+R_{2}(u)\leq {\frac {u^{2}}{8}}.$

Démonstration de l'inégalité de Hoeffding

On applique ensuite l'inégalité de Markov. Pour cela, on pose:

${\begin{array}{rl}Y_{i}&=X_{i}-\mathbb {E} [X_{i}],\\c_{i}&=a_{i}-\mathbb {E} [X_{i}],\quad d_{i}=b_{i}-\mathbb {E} [X_{i}],\end{array}}$

et on remarque que

${\begin{array}{rl}\mathbb {P} (c_{i}\leq Y_{i}\leq d_{i})&=1,\\d_{i}-c_{i}&=b_{i}-a_{i},\\S_{n}-\mathbb {E} [S_{n}]&=Y_{1}+Y_{2}+\dots +Y_{n}.\end{array}}$

Pour tout $\ s>0,\$ on a donc, en vertu d'un corollaire de l'inégalité de Markov, de l'indépendance des $\ X_{i},\$ et donc des $\ Y_{i},\$ et de la proposition précédente :

${\begin{array}{rl}\mathbb {P} \left(S_{n}-\mathbb {E} [S_{n}]\geq t\right)&\leq \mathbb {E} \left[e^{s(S_{n}-\mathbb {E} [S_{n}])}\right]e^{-st}\\&=\mathbb {E} \left[e^{s(Y_{1}+Y_{2}+\dots +Y_{n})}\right]e^{-st}\\&=e^{-st}\ \prod _{i=1}^{n}\mathbb {E} \left[e^{sY_{i}}\right]\\&\leq \exp \left(-st+{\frac {s^{2}\ \sum _{i=1}^{n}(b_{i}-a_{i})^{2}}{8}}\right).\end{array}}$

L'inégalité est en particulier vraie pour

$s_{0}={\frac {4t}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}},$

qui réalise le minimum de la borne de droite, ce qui démontre la première inégalité. La deuxième inégalité se démontre en remplaçant $\ Y_{i}\$ par $\ Y_{i}^{\prime }=\mathbb {E} [X_{i}]-X_{i},\$ et $\ S_{n}-\mathbb {E} [S_{n}]\$ par $\ \mathbb {E} [S_{n}]-S_{n},\$ dans le calcul précédent, en posant

${\begin{array}{rl}c_{i}^{\prime }&=\mathbb {E} [X_{i}]-b_{i},\\d_{i}^{\prime }&=\mathbb {E} [X_{i}]-a_{i},\end{array}}$

et en remarquant que

${\begin{array}{rl}\mathbb {P} (c_{i}^{\prime }\leq Y_{i}^{\prime }\leq d_{i}^{\prime })&=1,\\d_{i}^{\prime }-c_{i}^{\prime }&=b_{i}-a_{i},\\\mathbb {E} [S_{n}]-S_{n}&=Y_{1}^{\prime }+Y_{2}^{\prime }+\dots +Y_{n}^{\prime }.\end{array}}$

La troisième inégalité est une conséquence directe des deux premières.

Énoncé "en tout temps"

Dans son article de 1963, Hoeffding a donné un énoncé légèrement plus général de son inégalité, utilisant l'inégalité de Doob. Plus précisément, sous les mêmes hypothèses, pour tout $\ t>0,\$

${\begin{array}{rl}\mathbb {P} \left(\exists m\leq n,~S_{m}-\mathbb {E} [S_{m}]\geq t\right)&\leq \exp \left(-{\frac {2\,t^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right),\\\mathbb {P} \left(\exists m\leq n,~S_{m}-\mathbb {E} [S_{m}]\leq -t\right)&\leq \exp \left(-{\frac {2\,t^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right),\\\mathbb {P} \left(\exists m\leq n,~\left|S_{m}-\mathbb {E} [S_{m}]\right|\geq t\right)&\leq 2\exp \left(-{\frac {2\,t^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right).\end{array}}$

Voir aussi

Pages liées

• Inégalité d'Azuma
• Inégalité de Markov
• Inégalité de Bienaymé-Tchebychev

Bibliographie

• C. McDiarmid, On the method of bounded differences. In Surveys in Combinatorics, London Math. Soc. Lectures Notes 141, Cambridge Univ. Press, Cambridge 1989, 148–188.
• W. Hoeffding, "Probability inequalities for sums of bounded random variables", J. Amer. Statist. Assoc. 58, 13–30, 1963